Search for: All records

Abstract How many copies of a fixed odd cycle, , can a planar graph contain? We answer this question asymptotically for and prove a bound which is tight up to a factor of 3/2 for all other values of . This extends the prior results of Cox and Martin and of Lv, Győri, He, Salia, Tompkins, and Zhu on the analogous question for even cycles. Our bounds result from a reduction to the following maximum likelihood question: which probability mass on the edges of some clique maximizes the probability that edges sampled independently from form either a cycle or a path? 

An ordered graph is a graph with a linear ordering on its vertices. The online Ramsey game for ordered graphs $$G$$ and $$H$$ is played on an infinite sequence of vertices; on each turn, Builder draws an edge between two vertices, and Painter colors it red or blue. Builder tries to create a red $$G$$ or a blue $$H$$ as quickly as possible, while Painter wants the opposite. The online ordered Ramsey number $$r_o(G,H)$$ is the number of turns the game lasts with optimal play. In this paper, we consider the behavior of $$r_o(G,P_n)$$ for fixed $$G$$, where $$P_n$$ is the monotone ordered path. We prove an $$O(n \log n)$$ bound on $$r_o(G,P_n)$$ for all $$G$$ and an $O(n)$ bound when $$G$$ is $$3$$-ichromatic; we partially classify graphs $$G$$ with $$r_o(G,P_n) = n + O(1)$$. Many of these results extend to $$r_o(G,C_n)$$, where $$C_n$$ is an ordered cycle obtained from $$P_n$$ by adding one edge. 

Abstract A$$(p,q)$$-colouring of a graph$$G$$is an edge-colouring of$$G$$which assigns at least$$q$$colours to each$$p$$-clique. The problem of determining the minimum number of colours,$$f(n,p,q)$$, needed to give a$$(p,q)$$-colouring of the complete graph$$K_n$$is a natural generalization of the well-known problem of identifying the diagonal Ramsey numbers$$r_k(p)$$. The best-known general upper bound on$$f(n,p,q)$$was given by Erdős and Gyárfás in 1997 using a probabilistic argument. Since then, improved bounds in the cases where$$p=q$$have been obtained only for$$p\in \{4,5\}$$, each of which was proved by giving a deterministic construction which combined a$$(p,p-1)$$-colouring using few colours with an algebraic colouring. In this paper, we provide a framework for proving new upper bounds on$$f(n,p,p)$$in the style of these earlier constructions. We characterize all colourings of$$p$$-cliques with$$p-1$$colours which can appear in our modified version of the$$(p,p-1)$$-colouring of Conlon, Fox, Lee, and Sudakov. This allows us to greatly reduce the amount of case-checking required in identifying$$(p,p)$$-colourings, which would otherwise make this problem intractable for large values of$$p$$. In addition, we generalize our algebraic colouring from the$$p=5$$setting and use this to give improved upper bounds on$$f(n,6,6)$$and$$f(n,8,8)$$.